package q416_canPartition;

public class Solution_1 {
    /**
     * 为什么这道题能够成为一个背包问题？
     * 首先我们需要了解 在滚动数组解决背包问题的情况下 dp[i] 是指背包重量为i的情况下能够装的最大价值
     * 这道题中我们放入的数的值就是它的价值，也是它的重量
     * 1 dp[i]有一个显著的特点 就是它不能放 *超过*  i 的数
     * 2 同时还有一个特点 我们背包问题一定求出的是能够装的 *最大* 价值
     * 那么在这题中 我们的dp[maxNum]也是指容量maxNum能够装最大的数
     * 要么就是小于maxNum 要么就是等于 所以才能够用背包问题的方法求解
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }

        int maxNum = sum / 2;
        int[] dp = new int[maxNum + 1];
        for(int i = 0; i < nums.length; i++) { // 遍历所有我们能用的数
            for(int j = maxNum; j >= nums[i]; j--) { // 遍历我们dp的容量 注意要倒序遍历 并且条件要是j >= nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[maxNum] == maxNum;
    }
}
